1. Field of the Invention
The present invention relates to computer networks and distributed computing systems. More specifically, the present invention relates to a method and an apparatus for forwarding a packet fragment to a destination node, wherein the destination node is determined based upon information within a first fragment of the packet.
2. Related Art
The recent explosive growth of electronic commerce has led to a proliferation of web sites on the Internet selling products as diverse as toys, books and automobiles, and providing services, such as insurance and stock trading. Millions of consumers are presently surfing through web sites in order to gather information, to make purchases, or purely for entertainment.
The increasing traffic on the Internet often places a tremendous load on the servers that host web sites. Some popular web sites receive over a million xe2x80x9chitsxe2x80x9d per day. In order to process this much traffic without subjecting web surfers to annoying delays in retrieving web pages, it is advantageous to distribute the traffic between multiple server nodes, so that the multiple server nodes can operate in parallel to process the traffic.
In designing such a system to distribute traffic between multiple server nodes, a number of characteristics are desirable. It is desirable for such a system to be efficient in order to accommodate as much traffic as possible with a minimal response time. It is desirable for such a system to be xe2x80x9cscalable,xe2x80x9d so that additional server nodes can be added as demand for a service increases. In doing so, it is important to ensure that response time does not increase.
A system that distributes traffic between multiple server nodes typically performs a number of tasks. Upon receiving a packet containing data from another computer system, the system looks up a service that the packet is directed to. Once the service is determined, the system distributes workload involved in providing the service between the server nodes that are able to provide the service.
For efficiency reasons it is important to ensure that packets originating from the same client are directed to the same server. This requirement is complicated by the fact that a packet is typically divided into a number of fragments for transmission across a network; these fragments are reassembled at the server node to restore the original packet. Unfortunately, the client address (which can be used to identify the client) is typically stored in a header of the packet, which only appears in the first fragment of the packet. Furthermore, the fragments of a packet can be received in any order. Hence, a forwarding mechanism must somehow keep track of how packet fragments are associated with destination nodes.
This can be accomplished by reassembling a packet at the forwarding node to obtain the client address. This allows the forwarding node to determine where to send the packet to. However, forwarding packet fragments in this way can be very inefficient because the packet is likely be divided into fragments again for transmission from the forwarding node to the destination node.
What is needed is a method and an apparatus for forwarding packet fragments to a destination node, wherein the destination node can be determined from a first fragment of a packet.
One embodiment of the present invention provides a system that facilitates forwarding fragments of a packet received from a source node to a destination node, wherein the destination node is determined based upon information within a first fragment of the packet. The system operates by receiving at least one fragment of the packet at an interface node from the source node. The system uses a packet identifier from the fragment to look up an entry for the packet within a packet forwarding data structure. If this entry specifies the destination node, the system forwards the fragment to the destination node. If the entry does not specify the destination node, and if the fragment is not the first fragment of the packet, the system links the fragment into the entry for the packet within the packet forwarding data structure, so that the fragment can be forwarded to the destination node when the destination node later becomes known.
In one embodiment of the present invention, if the entry for the packet does not specify the destination node, and if the fragment is the first fragment of the packet, the system: determines the destination node from information contained within the first fragment; initializes the entry for the packet to specify the destination node; and forwards any fragments linked into the entry as well as the first fragment to the destination node.
In one embodiment of the present invention, if an entry for the packet does not exist within the packet forwarding data structure, the system creates an entry for the packet. In a variation on this embodiment, creating the entry for the packet involves starting a timer for the entry. When this timer expires, the system removes the entry from the packet forwarding data structure.
In one embodiment of the present invention, if an entry for the packet does not exist within the packet forwarding data structure, and if the fragment is the first fragment of the packet, the system determines the destination node from the information contained within the first fragment; initializes the entry for the packet to specify the destination node; and forwards the first fragment to the destination node.
In one embodiment of the present invention, and if an entry for the packet does not exist within the packet forwarding data structure, and if the fragment is not the first fragment of the packet, the system links the fragment into the entry for the packet within the packet forwarding data structure, so that the fragment can be later forwarded to the destination node when the destination node becomes known.
In one embodiment of the present invention, the packet includes an identifier for an Internet Protocol (IP) packet; and the payload portion of the first fragment of the packet includes a transmission control protocol/user datagram protocol (TCP/UDP) header that is used to determine the destination node.